package lcr;

public class Test0054 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(0);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(8);

        treeNode4.left=treeNode1;
        treeNode4.right=treeNode6;
        treeNode1.left=treeNode;
        treeNode1.right=treeNode2;
        treeNode6.left=treeNode5;
        treeNode6.right=treeNode7;
        treeNode2.right=treeNode3;
        treeNode7.right=treeNode8;


        Solution0054_1 solution00541 = new Solution0054_1();
        System.out.println(solution00541.convertBST(treeNode4));
    }

}

class Solution0054_1 {
    public TreeNode convertBST(TreeNode root) {
        dfs(root,0);
        return root;
    }

    public int dfs(TreeNode node,int sum){
        if (node==null) return sum;

        int right = dfs(node.right,sum);
        node.val += right;
        return dfs(node.left, node.val);
    }
}